package pers.lls.hds.map;


/**
 * 拓扑排序
 *
 * @author lilichai
 */
public class TopoGraph {
    private final int MAX_VERTS = 20;
    private TopoVertex TopoVertexList[];
    private int adjMat[][];
    private int nVerts;
    private char sortedArray[];

    public TopoGraph() {
        TopoVertexList = new TopoVertex[MAX_VERTS];

        adjMat = new int[MAX_VERTS][MAX_VERTS];
        nVerts = 0;
        for (int j = 0; j < MAX_VERTS; j++)
            for (int k = 0; k < MAX_VERTS; k++)
                adjMat[j][k] = 0;
        sortedArray = new char[MAX_VERTS];
    }

    public void addTopoVertex(char lab) {
        TopoVertexList[nVerts++] = new TopoVertex(lab);
    }

    public void addEdge(int start, int end) {
        adjMat[start][end] = 1;
    }

    public void displayTopoVertex(int v) {
        System.out.print(TopoVertexList[v].label);
    }

    public void topo() {
        int orig_nVerts = nVerts;

        while (nVerts > 0) {

            int currentTopoVertex = noSuccessors();
            if (currentTopoVertex == -1) {
                System.out.println("ERROR: TopoGraph has cycles");
                return;
            }

            sortedArray[nVerts - 1] = TopoVertexList[currentTopoVertex].label;

            deleteTopoVertex(currentTopoVertex);
        }

        System.out.print("Topologically sorted order: ");
        for (int j = 0; j < orig_nVerts; j++)
            System.out.print(sortedArray[j]);
        System.out.println("");
    }

    public int noSuccessors() {
        boolean isEdge;

        for (int row = 0; row < nVerts; row++) {
            isEdge = false;
            for (int col = 0; col < nVerts; col++) {
                if (adjMat[row][col] > 0) {
                    isEdge = true;
                    break;
                }
            }
            if (!isEdge)
                return row;
        }
        return -1;
    }

    public void deleteTopoVertex(int delVert) {
        if (delVert != nVerts - 1) {
            for (int j = delVert; j < nVerts - 1; j++)
                TopoVertexList[j] = TopoVertexList[j + 1];

            for (int row = delVert; row < nVerts - 1; row++)
                moveRowUp(row, nVerts);

            for (int col = delVert; col < nVerts - 1; col++)
                moveColLeft(col, nVerts - 1);
        }
        nVerts--;
    }

    private void moveRowUp(int row, int length) {
        for (int col = 0; col < length; col++)
            adjMat[row][col] = adjMat[row + 1][col];
    }

    private void moveColLeft(int col, int length) {
        for (int row = 0; row < length; row++)
            adjMat[row][col] = adjMat[row][col + 1];
    }

    public static void main(String[] args) {
        TopoGraph theTopoGraph = new TopoGraph();
        theTopoGraph.addTopoVertex('A');
        theTopoGraph.addTopoVertex('B');
        theTopoGraph.addTopoVertex('C');
        theTopoGraph.addTopoVertex('D');
        theTopoGraph.addTopoVertex('E');
        theTopoGraph.addTopoVertex('F');
        theTopoGraph.addTopoVertex('G');
        theTopoGraph.addTopoVertex('H');

        theTopoGraph.addEdge(0, 3);
        theTopoGraph.addEdge(0, 4);
        theTopoGraph.addEdge(1, 4);
        theTopoGraph.addEdge(2, 5);
        theTopoGraph.addEdge(3, 6);
        theTopoGraph.addEdge(4, 6);
        theTopoGraph.addEdge(5, 7);
        theTopoGraph.addEdge(6, 7);

        theTopoGraph.topo();
    }

}

class TopoVertex {
    public char label;

    public TopoVertex(char lab) {
        label = lab;
    }
}

